package heap

// 返回一个bool值，表示第i个元素是否应该排在第j个元素之前
func findKthLargest(nums []int, k int) int {
	n := len(nums)
	return quickselect(nums, 0, n - 1, n - k)
}

func quickselect(nums []int, l, r, k int) int {
	if l == r {
		return nums[k]
	}
	partition := nums[l] // 对比的值
	i := l - 1
	j := r + 1
	for i < j {
		for i++; nums[i] < partition; i++ {}
		for j--; nums[j] > partition; j-- {}
		if i < j {
			nums[i], nums[j] = nums[j], nums[i]
		}
	}
	if k <= j {
		return quickselect(nums, l, j, k)
	}else {
		return quickselect(nums, j + 1, r, k)
	}
}